/**
 * //返回与给定的前序和后序遍历匹配的任何二叉树。
 * //
 * // pre 和 post 遍历中的值是不同的正整数。
 * //
 * //
 * //
 * // 示例：
 * //
 * // 输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
 * //输出：[1,2,3,4,5,6,7]
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= pre.length == post.length <= 30
 * // pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列
 * // 每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。
 * //
 * // Related Topics 树 数组 哈希表 分治 二叉树 👍 201 👎 0
 */

package com.xixi.dataStructure.tree.binaryTree;

import com.xixi.dataStructure.tree.TreeNode;

public class ID00889ConstructBinaryTreeFromPreorderAndPostorderTraversal {
    public static void main(String[] args) {
        Solution solution = new ID00889ConstructBinaryTreeFromPreorderAndPostorderTraversal().new Solution();
    }


//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {

//        int[] p = {1, 2, 4, 5, 3, 6, 7};
//        int[] i = {4, 5, 2, 6, 7, 3, 1};
//
//        public Solution() {
//            constructFromPrePost(p, i);
//        }

        public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {

            return assembleTreeNode(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);
        }

        public TreeNode assembleTreeNode(int[] preorder, int preFrom, int preTo, int[] postorder, int postFrom, int postTo) {
            if (preFrom == preTo && postFrom == postTo) return new TreeNode(preorder[preFrom]); //如果没有子树了，就返回当前树；
            if (preFrom > preTo || postFrom > postTo) return null; //如果没有子树了，就返回当前树；

            //先从preorder确定根节点
            int rootVal = preorder[preFrom];
            TreeNode root = new TreeNode(rootVal);

            //确定左子树
            int leftIndex = 0; //左子树偏移量
            //左子树值
            int leftVal = preorder[preFrom + 1]; //前序子集往前一格
            while (leftIndex <= postTo - 1) { //找到左子树边界值
                if(postorder[postFrom + leftIndex] == leftVal){
                    break;
                }
                ++leftIndex;
            }
            //左子树（包含左根节点）范围是 [ preFrom + 1 ： preFrom + 1 + leftIndex], [postFrom : postFrom + leftIndex]
            root.left = assembleTreeNode(preorder, preFrom + 1, preFrom + 1 + leftIndex, postorder, postFrom, postFrom + leftIndex);


            //右子树值
            if (postFrom + leftIndex < postTo - 1) { //小于才会出现右子树
                int rightVal = preorder[preFrom + 1 + leftIndex + 1]; //左子树的范围往右一格
                root.right = assembleTreeNode(preorder, preFrom + 1 + leftIndex + 1, preTo, postorder, postFrom + leftIndex + 1, postTo -1 );

            }

            return root;

        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}